def longest_palindromic_substring(s):
    """找到并返回最长的回文子串"""
    n = len(s)
    if n == 0:
        return ""
    
    # dp[i][j] 表示 s[i:j+1] 是否是回文串
    dp = [[False] * n for _ in range(n)]
    max_len = 1
    start = 0
    
    # 所有长度为 1 的子串都是回文串
    for i in range(n):
        dp[i][i] = True
    
    # 检查长度为 2 的子串
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            max_len = 2
            start = i
    
    # 检查长度大于 2 的子串
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                if length > max_len:
                    max_len = length
                    start = i
    
    return s[start:start + max_len]
